#include <iostream>

using namespace std;

int *a;
int len;

void merge(int low, int mid, int high);

void merge_sort(int low,int high) {
	int mid;
	if(low < high) {
		mid=(low + high) / 2;
		merge_sort(low, mid);			// Immer schoen in 2 Teile austeilen
		merge_sort(mid+1, high);
		merge(low, mid, high);
	}
}

void merge(int low, int mid, int high) {
	int * b = new int[len];
	int h, i, j, k;
	h = low;
	i = low;
	j = mid + 1;

	while((h <= mid) && (j <= high)) { 	// immer das oberste element vergleichen
		if(a[h]<= a[j]) {				// und kleineres in hilfsarray rein
			b[i] = a[h];
			h++;
		}
		else {
			b[i] = a[j];
			j++;
		}
		i++;
	}
 
	if(h > mid) {						// Wenn ein Array "leer" ist die das restliche
		for(k = j; k <= high; k++) {	// andere Array ins Hilfsarray rein
			b[i] = a[k];
			i++;
		}
	} else {
		for(k = h; k <= mid; k++) {
			b[i] = a[k];
			i++;
		}
	}
	
	for(k = low; k <= high; k++) 		// sortiertes hilfsarray in normales array zurueck
		a[k] = b[k];

	//delete [] b;
}

int * random(int num) {
	int * p = new int[num];

	for (int i=0; i<num; i++) {
		p[i] = rand();
	}

	return p;
}

int main() {
	int num,i;

	cout << "********************************************************************************" << endl;
	cout << "                             MERGE SORT PROGRAM" << endl;
	cout << "********************************************************************************" << endl;
 	cout << endl << endl;
	cout << "Please Enter THE NUMBER OF ELEMENTS you want to sort [THEN PRESS ENTER]:" << endl;
	
	cin >> num;
	len = num;
	a = random(num);
	
	merge_sort(1, num);

	cout << endl;
	cout << "So, the sorted list (using MERGE SORT) will be :" << endl;
	cout << endl << endl;

	for(i = 1; i <= num; i++)
		cout << a[i] << " ";


	return 0;
}

